L1-028 判断素数

题目 L1-028 判断素数

思路分析

基础质数

判断质数

合数成对出现 只需判断前半段

使用i≤n/i 效率高于sqrt(n) 避免出现i*i≤n的越界危险

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i <= n / i;i ++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

筛法

埃氏筛
从2开始 把所有质数的倍数都筛掉 没被筛的就是质数 保存起来
void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]){ //可以用质数就把所有的合数都筛掉;
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i)
                st[j]=true;
        }
    }
}
//用set方便些
set<int> primes;
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!isnot_prime[i]){
            primes.insert(i);
            for(int j=i;j<=n;j+=i)
                isnot_prime[j]=true;
        }
    }
}

线性筛
只需要用最小的质因数进行筛除
注意避免重复标记if(i%primes[j]==0)
10^7用线性筛
void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i])
            primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
                break;
        }
    }
}

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf=0x3f3f3f3f;

bool is_prime(int n){

	if(n<2)	return false;

	for(int i=2;i<=n/i;i++){

		if(n%i==0)	return false;

	}

	return true;

}

//const int N=1000010;

//set<int> primes;

//bool isnot_prime[N];

//void get_primes(int n){

//	for(int i=2;i<=n;i++){

//		if(!isnot_prime[i]){

//			primes.insert(i);

//			for(int j=i;j<=n;j+=i){

//				isnot_prime[j]=true;

//			}

//		}

//	}

//}

signed main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

//	get_primes(N);

	while(n--){

		int tmp;cin>>tmp;

		if(is_prime(tmp))	cout<<"Yes"<<endl;

		else	cout<<"No"<<endl;

//		if(primes.find(tmp)!=primes.end())	cout<<"Yes"<<endl;

//		else	cout<<"No"<<endl;

	}

	return 0;

}

同类题型

视频讲解

⬅️ L1-027 出租 🏠 00-天梯赛 ➡️ L1-029 是不是太胖了